\documentclass{ctexart}
\usepackage[hidelinks]{hyperref}%目录
\usepackage{listing}
\usepackage{xeCJK} %导入这个宏包，就可以支持中文
\usepackage{cite}%文献引用
\usepackage{graphicx}
\usepackage{amsthm,amsmath,amssymb,amsfonts}%数学命题，数学字母，排版
\usepackage[a4paper,left=25.4mm,right=25.4mm,top=29.8mm,bottom=29.8mm]{geometry}
\pagestyle{myheadings}
\numberwithin{equation}{section}%以section编号equation
%数学命题环境定义 
%证明环境直接用proof
\theoremstyle{plain} \newtheorem{thm}{定理}[section]
\theoremstyle{plain} \newtheorem*{lemma}{引理}
\theoremstyle{plain} \newtheorem*{prop}{prop}
\theoremstyle{plain} \newtheorem*{property}{性质}
\theoremstyle{definition} \newtheorem*{define}{定义}
\theoremstyle{plain} \newtheorem*{cor}{cor}
\theoremstyle{plain} \newtheorem*{eg}{例}


\title{Data Structure}
\author{陈宇涛,强数2101,3210102287}

\begin{document}
\maketitle

\section*{Homework3 : Avl sorting}
\markright{Data Structure}


\subsection*{问题描述}
\begin{flushleft}
  ~~~Write a function that takes as input a binary search tree, T, and two keys k1 and k2,
which are ordered so that k1 ≤ k2, and prints all elements X in the tree such that
$k1 \le Key(X) \le k2$. \\
~~~Do not assume any information about the type of keys except
that they can be ordered (consistently). Your program should run in $O(K + logN)$
average time, where K is the number of keys printed. Bound the running time of
your algorithm.
\end{flushleft}





\subsection*{设计思路和理论分析}
   \begin{verbatim}
    具体实现private:
    Internal method to print node in a fixed internal [a,b]
    
    void printrange(const Comparable &inf,const Comparable &sup,AvlNode * t) 
  {
    if( t != nullptr )
    {
      if( inf <= t->element)
        printrange( inf, sup, t->left );
      if( inf <= t->element && t->element <= sup )
	 cout<< t->element << " " ;
      if( t->element <= sup )
        printrange( inf , sup , t->right );
    }  
  }
   \end{verbatim}



   \begin{flushleft}
    我们首先直接把BinarySearchTree看成Avltree,所以这棵树基本上是对称的满树。
    当其中有N个节点时，树的高度是$log(N)$。\\
    ~~对于程序的基本观察:\\
    (1)~~当printrange()从root开始查找到第一个位于区间内的节点之前,它只会执行printrange(t -> left) 的操作直到碰到第一个需要的节点.\\
    (2)~~ 当printrange()找到了最后一个位于区间内的节点后,它只会执行printrange(t -> right) 的操作直到碰到最底层的叶子.\\


    当$ k = o(logN) ~,~ 2^k = o(N)$ 时,即需要被输出的节点个数远远小于树的高度。\\
    我们假设最差情况k个结点至多分布在了某k层当中,我们发现这k层是连续的，从而
    时间复杂度
    \[
      T(N,k) < 2^{k} + log(N) ~~\Longrightarrow~~ T(N,k) = O( log(N) )
    \]

    当$ logN = o(k)~, ~ N = o(2^k)$时，即这棵树的高度远远小于需要输出的节点数k。至多$N - k$ 层发现第一个所需节点，当大量的节点被找到并输出。同样有这些节点所在层是连续分布的，所以当发现第一个节点后几乎处处执行输出t->element工作。
    \[
      T(N,k) <  k + log(N-k) ~~\Longrightarrow~~ T(N,k) = O( k + log(N) )
    \]
   \end{flushleft}




\subsection*{数值结果分析}
  \begin{table}[!ht]
    \centering
    \begin{tabular}{|l|l|l|l|l|l|l|}
    \hline
        N & logN / K  & 1     & 10     &   100  & $10^3$ & $10^4$ \\ \hline
        $10^3$ & 10   &5e-6   & 2.1e-5 & 1.7e-5 & /      & / \\ \hline
        $10^6$ & 20   & 2.8e-6  & 8e-5 &  2.2e-5    & 1.9e-4 & 2.6e-3\\ \hline
        $10^8$ & 30   & 5e-5&   1e-5    & 6e-5   & 4.1e-4    & 3.96e-3 \\ \hline
    \end{tabular}
\end{table}

\begin{flushleft}
  
  ~~在多次平均下得到上表，基本反映了$O(k+ logN)$的复杂度。\\
 
  ~~尤其是其中横向的对比：方便期间我将统一的随机打乱的数据放入AvlTree。当检索同样规模的树，单一改变需要查找的区间数据规模，发现时间复杂度随着k增大而增大,又由于$ k >> logN$,所以运行时间和N的关系不大,这也能够从纵向的对比下运行时间基本都是一个数量级的这一点看出。\\
  ~~但是由于再调大logN的值,N会变得非常巨大导致运行时间过长,所以对于$logN >> k$时情形体现得不充分。\\
\end{flushleft}


\end{document}